package com.ztom.offer.v2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树中和为某一值的路径
 * <p>
 * https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 *
 * @author ZhangTao
 */
public class Code34PathSum {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        dfs(root, path, target, res);
        return res;
    }

    private void dfs(TreeNode node, LinkedList<Integer> path, int target, List<List<Integer>> res) {
        if (node == null) {
            return;
        }
        path.offerLast(node.val);
        target -= node.val;
        // 必须是叶子节点
        if (target == 0 && node.left == null && node.right == null) {
            res.add(new ArrayList<>(path));
        }
        dfs(node.left, path, target, res);
        dfs(node.right, path, target, res);
        // 回溯
        path.pollLast();
    }
}
